from time import clock
# A bloody large number.
INFINITY = 1.0e400

class AnyTimeAlphaBetaSearch:
    '''
    This search algorithm implements the limited-resource minimax tree search 
    algorithm with alpha-beta pruning for zero-sum games. This version cuts off 
    search by depth alone and uses an evaluation function (utility).
    '''
    
    def __init__(self, player, max_depth, utility, turn_time_limit):
        '''
        Constructor.
        
        @param player: Your player. This search algorithm will choose the best
                       actions for this player.
        @param max_depth: The depth of the search tree.
        @param utility: An evaluation function for states.
        '''
        self.player = player
        self.max_depth = max_depth
        self.utility = utility
        
        self.timeBuffer = 0.03
        self.turnTime = turn_time_limit
        
    
    def search(self, current_state):
        '''
        Search game to determine best action; use alpha-beta pruning.
        
        @param current_state: The current game state to start the search from.
        '''
        self.depthLimit = self.max_depth
        self.endTime = clock() + self.turnTime - self.timeBuffer
        successors = current_state.getSuccessors().items()
        self.bestAction = successors[0][0]
        successors[0][1].winner = 0
        self.bestValue = self.utility(successors[0][1], self.endTime)
        
        while True:
            for action, state in successors:
                self.currentAction = action
                value_fn = self._getValueFn(state)
                try:
                    value = value_fn(state, self.bestValue, INFINITY, 1)
                except Exception, e:
                    if e[1] > self.bestValue:
                        return self.currentAction
                    return self.bestAction
                if value > self.bestValue:
                    self.bestValue = value
                    self.bestAction = action
            self.depthLimit += 1
            if self.endTime-clock() < 0:
                return self.bestAction
        return self.bestAction
    
    def _getValueFn(self, state):
        state.winner = 0
        if state.getCurrentPlayer() == self.player:
            return self._maxValue
        else:
            return self._minValue
    
    def _cutoffTest(self, state, depth):
        return depth >= self.depthLimit or (state.getWinner() is not None)
    
    def _maxValue(self, state, alpha, beta, depth):
        self.checkTime(self.bestValue)
        utility = self.utility(state, self.endTime)
        if self._cutoffTest(state, depth):
            return utility
        if utility > self.bestValue:
            self.bestValue = utility
            self.bestAction = self.currentAction
        
        value = utility
        self.checkTime(value)
        # reorder the successors.
        successors = state.getSuccessors().items()
        self.checkTime(value)
        for action,successor in successors:
            value_fn = self._getValueFn(successor)
            value = max(value, value_fn(successor, alpha, beta, depth + 1))
            if value >= beta:
                return value
            alpha = max(alpha, value)
            self.checkTime(value)
        return value
    
    def _minValue(self, state, alpha, beta, depth):
        self.checkTime(self.bestValue)
        utility = self.utility(state, self.endTime)
        if self._cutoffTest(state, depth):
            return utility
        if utility > self.bestValue:
            self.bestValue = utility
        
        value = utility
        self.checkTime(value)
        # reorder the successors.
        successors = state.getSuccessors().items()
        self.checkTime(value)
        for action,successor in successors:
            value_fn = self._getValueFn(successor)
            value = min(value, value_fn(successor, alpha, beta, depth + 1))
            if value <= alpha:
                return value
            beta = min(beta, value)
            self.checkTime(value)
        return value
    
    def checkTime(self,value):
        if self.endTime-clock() < 0:
            raise Exception("Timeout",value)
